package com.wngbms.leetcode;

import java.util.*;

/**
 * 二叉树 中序遍历
 */
public class _94 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return null;
        }

        List<Integer> res = new ArrayList<>();

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;

        while (!(curr.left == null && curr.right == null && stack.isEmpty())) {
            TreeNode left = curr.left;
            TreeNode right = curr.right;

            if (left != null) {
                stack.addFirst(left);
                curr = left;
                continue;
            }

            res.add(curr.val);

            if (right != null) {
//                curr
            }
        }

        return null;
    }

    public void traversal(TreeNode root) {

        TreeNode left = root.left;
        if (left != null) {
            traversal(left);
        }

        final int val = root.val;

        TreeNode right = root.right;
        if (right != null) {
            traversal(right);
        }
    }

    public static List<Integer> preorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        TreeNode curr = null, left = null, right = null;

        while ((curr = stack.poll()) != null) {
            res.add(curr.val);

            left = curr.left;
            right = curr.right;
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
        }

        return res;
    }

    public static List<Integer> postorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> res_stack = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();

        TreeNode curr = null, left = null, right = null;
        stack.push(root);

        while ((curr = stack.poll()) != null) {
            left = curr.left;
            right = curr.right;

            res_stack.push(curr);
            if (left != null) {
                stack.push(left);
            }
            if (right != null) {
                stack.push(right);
            }
        }

        while ((curr = res_stack.poll()) != null) {
            res.add(curr.val);
        }

        return res;
    }

    public static void main(String[] args) {
        TreeNode _1 = new TreeNode(1);
        TreeNode _2 = new TreeNode(2);
        TreeNode _3 = new TreeNode(3);
        TreeNode _4 = new TreeNode(4);
        TreeNode _5 = new TreeNode(5);
        TreeNode _6 = new TreeNode(6);
        TreeNode _7 = new TreeNode(7);

        _1.left = _2;
        _1.right = _3;

        _2.left = _4;
        _2.right = _5;

        _3.left = _6;
        _3.right = _7;

        System.out.println(preorder(_1));
        System.out.println(postorder(_1));
    }

}
